package com.sgg.datastructure.tree;

// 前序的
public class ThreadedBinaryTreePre {
    private HeroNode root;
    private HeroNode pre;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public static void main(String[] args) {
        HeroNode root = new HeroNode(1, "tom");
        HeroNode node2 = new HeroNode(3, "jack");
        HeroNode node3 = new HeroNode(6, "smith");
        HeroNode node4 = new HeroNode(8, "mary");
        HeroNode node5 = new HeroNode(10, "king");
        HeroNode node6 = new HeroNode(14, "dim");
        //二叉树，后面我们要递归创建, 现在简单处理使用手动创建   1,3,8,10,6,14
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        ThreadedBinaryTreePre tree = new ThreadedBinaryTreePre();
        tree.setRoot(root);
        tree.前序构建();
        System.out.println("前序");

        System.out.println(node5.getLeft());
        System.out.println(node5.getRight());
        System.out.println();



    }

    //遍历线索化二叉树的方法(中序)
    public void threadedList() {
        //定义一个变量，存储当前遍历的结点，从 root 开始
        HeroNode node = root;
        while (node != null) {
            //循环的找到 leftType == 1 的结点，第一个找到就是 8 结点,后面随着遍历而变化,因为当 leftType==1 时，说明该结点是按照线索化处理后的有效结点
            while (node.getLeftType() == 0) {
                node = node.getLeft();
            }
            //打印当前这个结点
            System.out.println(node);
            //如果当前结点的右指针指向的是后继结点,就一直输出
            while (node.getRightType() == 1) {
                //获取到当前结点的后继结点
                node = node.getRight();
                System.out.println(node);
            }
            //替换这个遍历的结点
            node = node.getRight();
        }
    }

    //作业:前序线索化树构建
    public void 前序构建() {
        前序构建(root);
    }

    public void 前序构建(HeroNode node) {
        if (node == null) {
            return;
        }
        //线索化当前结点[有难度]
        if (node.getLeft() == null) {
            //让当前结点的左指针指向前驱结点
            node.setLeft(pre);
            //修改当前结点的左指针的类型,指向前驱结点
            node.setLeftType(1);
        }
        //处理后继结点
        if (pre != null && pre.getRight() == null) {
            //让前驱结点的右指针指向当前结点
            pre.setRight(node);
            //修改前驱结点的右指针类型
            pre.setRightType(1);
        }
        //!!! 每处理一个结点后，让当前结点是下一个结点的前驱结点
        pre = node;
        //线索化左子树
        if (node.getLeftType() != 1) {
            前序构建(node.getLeft());
        }
        //线索化右子树
        if (node.getRightType()!= 1) {
            前序构建(node.getRight());
        }

    }

}
